package 链表.回文链表;

/**
 * 方法二
 * 回文将其拆成两半部分，然后将后半部分的反转，比较就可以了
 * 步骤如下
 * 1，找到链表的中心元素（前半部分的尾节点）
 * 如何实现呢，用快慢指针
 * 为什么能想到快慢指针呢
 * 要求中心 ，一个快指针，一个慢指针，快指针每次移动两步，
 * 慢指针每次移动一步，当快指针到达链表末尾时，慢指针到达链表的中心元素
 * 2，翻转后半部分列表
 * 只要指的方向改变，那么链表就会翻转
 * 首先定义一个指针prev指向null，然后定义一个指针prev指向head
 * 这样curr指向prev，哪么方向就会反转
 * 这就会又有一个问题
 * curr.next = prev;
 * prev = curr;
 * 这样的话链表就会断掉
 * 所以说要有个临时变量保存curr
 * 3，比较两半部分链表
 * 获取前半段链表的首节点
 * 获取后半段链表的首节点
 * 然后循环进行比较就可以了
 * */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        // 获取前半部分列表的尾节点
        ListNode first = feng(head);
        // 反转后半部分列表
        ListNode second = reverseList(first.next);
        // 对比两半部分链表
        ListNode p1 = head;
        ListNode p2 = second;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return result; // 补充返回结果
    }
    
    // 寻找链表中心元素（前半部分的尾节点），一分为二
    private ListNode feng(ListNode head) {
        ListNode kuai = head;
        ListNode man = head;
        while (kuai.next != null && kuai.next.next != null) {
            kuai = kuai.next.next;
            man = man.next;
        }
        return man;
    }
    
    // 反转后半部分的链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}